#ifndef GRAPH_H_
#define GRAPH_H_
#include <iostream>

/*图的表示分为两种, 一种是邻接矩阵, 一种是邻接表, 即数组后面附加单向链表.*/

/////////////////////////* Common use for two types */////////////////////////
#define MAXVEX     100		/* 最大顶点数，应由用户定义 */
#define INFINITY  65535		/* 表示权值的无穷*/

typedef int EdgeType;		/* 边上的权值类型应由用户定义 */
typedef char VertexType;	/* 顶点类型应由用户定义  */
/////////////////////////* Common use for two types */////////////////////////


//////////////////////////* 邻接矩阵 数据结构支持 *///////////////////
typedef struct
{
	VertexType vexs[MAXVEX];/* 顶点表 */
	EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
	int numNodes, numEdges;/* 图中当前的顶点数和边数  */
} MGraph;

/* 建立无向网图的邻接矩阵表示 */
void CreateMGraph(MGraph *Gp);
//////////////////////////* 邻接矩阵 数据结构支持 *///////////////////



//////////////////////////* 邻接表, 数据结构支持 *///////////////////
#if 1
typedef struct EdgeNode/* 边表结点  */
{
	int adjvex;/* 邻接点域,存储该顶点对应的下标 */
	EdgeType weight;/* 用于存储权值,对于非网图可以不需要 */
	struct EdgeNode *next; /* 链域,指向下一个邻接点 */
} EdgeNode;


typedef struct VextexNode/* 顶点表结点 */
{
	VertexType data;	/* 顶点域,存储顶点信息 */
	EdgeNode *firstedge;/* 边表头指针 */
} VextexNode, AdjList[MAXVEX];


typedef struct
{
	AdjList adjList;
	int numNodes, numEdges; /* 图中当前顶点数和边数 */
} GraphAdjList; 


void CreateALGraph(GraphAdjList *Gp);
#endif
//////////////////////////* 邻接表, 数据结构支持 *///////////////////


/*两种访问方式的遍历标记数组 */
extern bool visited[MAXVEX];/* 访问标志的数组 */

#if 1 //广度优先遍历,主要使用矩阵.
/* 邻接矩阵的广度遍历算法 */
void BFSTraverse(MGraph G); // Breadth First Search.

/*邻接表的广度优先遍历算法 */
void BFSTraverse(GraphAdjList *GL);
#endif


#if 1 //深度优先遍历,主要使用递归进行实现.

/* 邻接矩阵的深度优先递归算法 */
void DFS(MGraph MG, int i); 
void DFSTraverse(MGraph MG); // Depth First Search.

/* 邻接表的深度遍历操作 */
void DFS(GraphAdjList *GL, int i);
void DFSTraverse(GraphAdjList *GL);
#endif

#endif
